package nowcoder.nc37;

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 *   public Interval(int start, int end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */

public class Solution {
    public static void main(String[] args) {
        //        [[10,30],[20,60],[80,100],[150,180]]
        ArrayList<Interval> res=new ArrayList<>();
        res.add(new Interval(50,60));
        res.add(new Interval(80,100));
        res.add(new Interval(10,30));
        res.add(new Interval(150,180));
        res.add(new Interval(20,60));
        new Solution().merge(res);
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param intervals Interval类ArrayList 
     * @return Interval类ArrayList
     */
    public ArrayList<Interval> merge (ArrayList<Interval> intervals) {

        ArrayList<Interval> res=new ArrayList<>();
        if (intervals.size()==0)return intervals;
        // write code
        sort(intervals);
        int j=1;
        Interval interval=intervals.get(0);
        for (; j<intervals.size() ; ) {
            if (interval.end >= intervals.get(j).start) {
                if (interval.end < intervals.get(j).end){
                    interval.end=intervals.get(j).end;
                }
                j++;
                continue;
            }else {
                res.add(interval);
                interval= intervals.get(j);
                j++;
            }

        }
        if (interval!=null){
            res.add(interval);
        }

        return res;
    }

    static void sort(List<Interval> intervals){
        Collections.sort(intervals,(a,b)->{
            if (a.start > b.start) return 1;
            else if (a.start < b.start) return -1;
            return a.end - b.end;
        });
    }

    static void quickSort(List<Interval> items, int start, int end) {
        if (start >= end) {
            return;
        }
        int middle = patition(items, start, end);
        quickSort(items, start, middle - 1);
        quickSort(items, middle + 1, end);
    }
    //性能更差？
//    private static int patition(List<Interval> items, int start, int end) {
//        int l = start + 1, r = end, mid = start;
//        while (true) {
//            while (l <= r && compare(items.get(l), items.get(mid)) <= 0) l++;
//            while (l <= r && compare(items.get(r), items.get(mid)) > 0) r--;
//            if (l >= r) break;
//            Collections.swap(items, l, r);
//        }
//        Collections.swap(items, mid, r);
//        return r;
//    }

    private static int patition(List<Interval> items, int start, int end) {
        int l=start+1,r=end,mid=start;
        while (l<=r){
            if (compare(items.get(l),items.get(mid))<=0) {
                Collections.swap(items,l,mid);
                mid=l;
                l++;
            }
            else  {
                Collections.swap(items,l,r);
                r--;
            }
        }
        return mid;
    }

    static int compare(Interval a, Interval b) {
        if (a.start > b.start) return 1;
        else if (a.start < b.start) return -1;
        return a.end - b.end;
    }

}